本发明涉及一种外部网关协议的多路径建立和转发的方法,把全局性的路径标识作为一个路径属性,在路由信息中扩散,建立多路径,简化了与现有网络的兼容;以显式路由方式路由,多路径和单路径的转发表分开的方式,并可以采用定长查找方式,加快查询速度。本发明在域间路由建立多条路径,并通过数据包嵌入路径标识的显式路由方式转发数据,挺高了有效性和可靠性;同时路由协议改动较小,易于实现,网络资源消耗很小,并且易于与现有网络兼容。
1.一种外部网关协议的多路径建立和转发的方法,其特征在于:允许域间路由协议对同一目的选择多条路径,不同的路由经过不同自治域路径;每一条路由用一个路径标识标记,用其与其他到同一目的路由区分;路径标识是由本自治域到目的自治域顺次经过自治域路号组成的自治域路径的哈希得到的;通过协议的路由更新和对路由更新的处理完成多路径的建立;并得到以路径标识,出端口,下一跳路径标识三元组为转发项的多路径转发表;下一跳路径标识为沿路径的下一个自治域到目的自治域顺次经过自治域路号组成的自治域路径的哈希值;数据的发送端在多路径中选择路径,后续的路由器根据发送端选择的路径进行具体的转发。
2.如权利要求1所述的一种外部网关协议的多路径建立和转发的方法,其特征在于:所述的多路径转发方法为:数据的发送端,在多条路径中选择,并把所选的路径标识加入到数据的包头中;路由器接收到数据包后,查询多路径转发表,匹配路径标识后转发;在数据包离开一个自治域到下一个自治域时,边界路由器用下一跳路径标识替换数据包中的路径标识;但数据包到达目的自治域时,不再查询多路径转发表,而是查询单路径转发表,匹配目的地址,到达目的。技术领域
本发明涉及一种外部网关协议的多路径建立和转发的方法,属于计算机网络技术领域。
背景技术
现有的互联网是由若干的自治域(AS-Autonomousxa0System)组成的,域间路由协议主要是Boarderxa0Gatewayxa0Protocol(BGP),它负责把各个域的路由信息在域间扩散。BGP是一个路径矢量(Path-Vector)协议,因为在BGP的路由信息中包含着叫AS_path的路径属性,它记录了这条路径所经过的自治域号(ASxa0Number)。目前的BGP协议只允许到达同一目的,计算出一条路径信息,即单路径协议。而实际的互联网中存在非常丰富的路径,如果可以自如地在多条路径上传送数据,互联网的有效性和可靠性都会得到很大的提高。目前的Cisco公司和Juniper公司的Walton等人提出了运用BGP通告多路径的方法,也采用了路径标识(Pathxa0Identifier)的方式区分同一目的的多条路径,而其中的路径标识只是本地有效的标识,没有任何语义,无法进行辅助全局性选路。Rensselaerxa0Polytechnicxa0Institute大学的Kaur等人提出用全局有效的路径标识(PathID)标识路径,显式路由的方式路由,而其中把多路径转发表和传统的单路径转发表组成了一个转发表,以<目的前缀,入路径标识,出端口,出路径标识>组成,没有具体路径建立的过程。其中的查询的方式是先用最长前缀匹配的方式查询目的前缀,之后查询路径标识。这种方式效率较低,直接就可以查询路径标识就可以确定准发端口;并且这种转发表结构,占用空间也较大,因为有前缀不同,路径相同的表项。
发明内容
本发明的目的在于改进上述现有技术中的不足而提供一种外部网关协议的多路径建立和转发的方法。本发明的目的通过以下措施来达到:允许域间路由协议对同一目的选择多条路径,不同的路由经过不同自治域路径;每一条路由用一个路径标识(Pathxa0ID)标记,用其与其他到同一目的路由区分;路径标识是由本自治域到目的自治域顺次经过自治域路号组成的自治域路径(ASxa0Path)的哈希(hash)得到的;通过协议的路由更新和对路由更新的处理完成多路径的建立;并得到以<路径标识(Pathxa0ID),出端口(OutgoingInterface),下一跳路径标识(Nextxa0Pathxa0ID)>三元组为转发项的多路径转发表;下一跳路径标识为沿路径的下一个自治域到到目的自治域顺次经过自治域路号组成的自治域路径(ASxa0Path)的哈希值;数据的发送端在多路径中选择路径,后续的路由器根据发送端选择的路径进行具体的转发。其中多路径建立方法为:域间路由协议的路由更新中包含一个新的路径属性,路径标识属性;域间路由协议允许通告到达同一目的的多条路径,新路径不会直接替代原路径;路由器收到路由更新后,除判断网络层可达信息属性外,再判断路径标识属性,只有两个都与已收到的相同时,才替换以前的路径,否则认为是新路径。多路径转发方法为:数据的发送端,在多条路径中选择,并把所选的路径标识加入到数据的包头中;路由器接收到数据包后,查询多路径转发表,匹配路径标识后转发;因为路径标识是哈希值,可以利用定长匹配的查找算法,加快查找速度;在数据包离开一个自治域到下一个自治域时,边界路由器用下一跳路径标识替换数据包中的路径标识;但数据包到达目的自治域时,不再查询多路径转发表,查询传统的转发表,匹配目的地址,到达目的本发明的优点在于:(1)在域间路由建立多条路径,并通过数据包嵌入路径标识的显式路由方式转发数据,挺高了有效性和可靠性;(2)路由协议改动较小,易于实现,网络资源消耗很小,并且易于与现有网络兼容;(3)多路径表和单路径表分离,可用定长查找加速查找速度。
附图说明
图1为本发明工作的一个具体实施方式
具体实施方式
本发明把全局性的路径标识作为一个路径属性,在路由信息中扩散,建立多路径,简化了与现有网络的兼容;以显式路由方式路由,多路径和单路径的转发表分开的方式,并可以采用定长查找方式,加快查询速度。以下结合附图对本发明说明:如图1所示,三个自治域系统组成的网络,终端A与终端B进行通信。在图1中,附图标记1表示终端A;附图标记9表示终端B;附图标记3表示路由器R_a;附图标记8表示路由器R_h;附图标记4表示边界路由器BR_b;附图标记5表示边界路由器BR_c;附图标记6表示边界路由器BR_g;附图标记7表示边界路由器BR_f;附图标记12表示边界路由器BR_d;附图标记13表示边界路由器BR_e;附图标记2表示自治域AS₁附图标记10表示自治域AS₂;附图标记11表示自治域AS₃;附图标记14表示自治域AS₄。外部网关协议为每条路径增加Pathxa0ID属性,并建立相应的多路径BR_d得到目的到终端B的两条路径分别是AS₄AS₃AS₂、AS₄AS₂,其Pathxa0ID分别为hash(AS₄AS₃AS₂)、hash(AS₄AS₂)。BR_d可同时选择这两条路径,建立多路径转发表,并通告给BR_b。R_a可以得到AS₁AS₄AS₃AS₂、AS₁AS₄AS₂和AS₁AS₂,其PathID分别是hash(AS₁AS₄AS₃AS₂)、hash(AS₁AS₄AS₂)和hash(AS₁AS₂)。终端A向终端B发数据包,选择了路径AS₁AS₄AS₂,终端A将该路径的Pathxa0ID,即hash(AS₁AS₄AS₂)嵌入每个数据包内。当数据包离开自治域AS₁时,边缘路由器BR_b将数据包内的Pathxa0ID替换成其多路径转发表(表1)内的其对应项的Nextxa0Pathxa0ID,即hash(AS₄AS₂)。当数据包离开自治域AS₄时,边缘路由器BR_e将数据包内的Pathxa0ID替换成其多路径转发表(表2)内的其对应项的Nextxa0Pathxa0ID,即hash(AS₂)。但数据包进入到AS₂内,进直接查询传统的单路径转发表,到达终端B。表1 xa0xa0Pathxa0ID

xa0xa0Outgoing
xa0xa0Interface
xa0xa0Nextxa0Pathxa0ID

xa0xa0Hash(AS₁AS₄AS₃AS₂)
xa0xa0Port₁
xa0xa0Hash(AS₄AS₃AS₂)
xa0xa0Hash(AS₁AS₄AS₂)
xa0xa0Port₁
xa0xa0Hash(AS₄AS₂)
表2 xa0xa0Pathxa0ID

xa0xa0Outgoing
xa0xa0Interface
xa0xa0Nextxa0Pathxa0ID

xa0xa0Hash(AS₄AS₃AS₂)
xa0xa0Port₁
xa0xa0Hash(AS₂)
xa0xa0Hash(AS₄AS₂)
xa0xa0Port₂
xa0xa0Hash(AS₂)